"""
2389. 和有限的最长子序列
简单
相关标签
premium lock icon
相关企业
提示
给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。

子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。



示例 1：

输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：queries 对应的 answer 如下：
- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。
示例 2：

输入：nums = [2,3,4,5], queries = [1]
输出：[0]
解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。


提示：

n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 106
"""
import bisect
import heapq
from bisect import bisect_right
from typing import List


class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        ans = []
        sum1 = sum(nums)
        len1 = len(nums)
        #有序后可使用前缀和优化，通过二分查找
        for q in queries:
            tempLen = len1
            tempSum = sum1
            i = len1 - 1
            while q<tempSum:
                tempSum -= nums[i]
                i-=1
                tempLen-=1
            ans.append(tempLen)
        return ans

    def answerQueries_res1(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        for i in range(1, len(nums)):
            nums[i] += nums[i - 1]  # 原地求前缀和
        for i, q in enumerate(queries):
            queries[i] = bisect_right(nums, q)-1+1  # 复用 queries 作为答案 -1是上一个，+1是索引转数量
        return queries

if __name__ == '__main__':
    # print(Solution().answerQueries([4,5,2,1],[3,10,21]))
    # dp = [1,2,3,3,4]
    # print(bisect.bisect_right(dp,3))
    print(Solution().answerQueries_res1([4,5,2,1],[3]))

    dp = [1, 2, 3, 3, 4]
    print(bisect.bisect_left(dp,3))
    print(bisect_right(dp,3))
